package my.suveng.leetcode.stack;

import java.util.HashMap;
import java.util.Stack;

/**
 *
 * @author suwenguang
 **/
public class S20 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isValid("([[{}]])"));

        Integer i = 2;
        int i1 = i.compareTo(3);
        System.out.println(i1);
    }

    //给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
//
// 有效字符串需满足：
//
//
// 左括号必须用相同类型的右括号闭合。
// 左括号必须以正确的顺序闭合。
//
//
// 注意空字符串可被认为是有效字符串。
//
// 示例 1:
//
// 输入: "()"
//输出: true
//
//
// 示例 2:
//
// 输入: "()[]{}"
//输出: true
//
//
// 示例 3:
//
// 输入: "(]"
//输出: false
//
//
// 示例 4:
//
// 输入: "([)]"
//输出: false
//
//
// 示例 5:
//
// 输入: "{[]}"
//输出: true
// Related Topics 栈 字符串
// 👍 1682 👎 0


    //leetcode submit region begin(Prohibit modification and deletion)
    static class Solution {
        public static final HashMap<Character, Character> map = new HashMap<>();
        Stack<Character> stack = new Stack<>();

        static {
            map.put('(', ')');
            map.put('{', '}');
            map.put('[', ']');
        }

        public boolean isValid(String s) {

            if (s == null || s.equals("")) {
                return true;
            }

            char[] chars = s.toCharArray();

            for (char c : chars) {
                if (map.containsKey(c)) {
                    stack.push(c);
                } else {
                    if (!stack.isEmpty()) {
                        if (map.get(stack.peek()).equals(c)) {
                            // 唯一正确路径, 出到如果发现有右边括号的, 则开始比对, 如果都是对应的, 则一起出, 如果不对, 直接返回false
                            stack.pop();
                        } else {
                            // 一旦不对, 则false
                            return false;
                        }
                    } else {
                        // 如果字符还没完, 并且是右括号, 新栈完, 直接返回false
                        return false;
                    }
                }
            }

            return stack.isEmpty();
        }
    }

//leetcode submit region end(Prohibit modification and deletion)
}



